Max consecutive ones III

Time: O(N); Space: O(1); medium

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2

Output: 6

Explanation:

  • [1,1,1,0,0,1,1,1,1,1,1]

  • Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3

Output: 10

Explanation:

  • [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]

  • Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

  • 1 <= len(A) <= 20000

  • 0 <= K <= len(A)

  • A[i] is 0 or 1

Hints:

  1. One thing’s for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there’s no point in doing it, right? Think Sliding Window!

  2. Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?

  3. We don’t have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don’t actually have to flip the zeros here!).

  4. The way to shrink or expand a window would be based on the number of zeros that can still be flipped and so on.

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def longestOnes(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        result, i = 0, 0

        for j in range(len(A)):
            K -= int(A[j] == 0)

            while K < 0:
                K += int(A[i] == 0)
                i += 1
            result = max(result, j-i+1)

        return result

[2]:

s = Solution1()

A = [1,1,1,0,0,0,1,1,1,1,0]
K = 2
assert s.longestOnes(A, K) == 6

A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
K = 3
assert s.longestOnes(A, K) == 10